package com.cat.greedyAlgorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-number-of-people-to-teach/?envType=daily-question&envId=2025-09-10
 * @create 2025/9/10 09:17
 * @since JDK17
 */

public class Solution42 {
    public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
        List<HashSet<Integer>> sets = new ArrayList<>();
        int m = languages.length, k = friendships.length, ans = Integer.MAX_VALUE, cnt;
        for (int i = 0; i < m; i++) {   // 每个人会的语言都加入哈希表中
            HashSet<Integer> t = new HashSet<>();
            for (int language : languages[i]) {
                t.add(language);
            }
            sets.add(t);
        }
        boolean[] h = new boolean[k], hp = new boolean[m + 1];
        for (int i = 0; i < k; i++) {
            int a = friendships[i][0], b = friendships[i][1];
            HashSet<Integer> setA = sets.get(a - 1), setB = sets.get(b - 1);
            for (var num : setA) {
                if (setB.contains(num)) {   // 有交集
                    h[i] = true;
                    break;
                }
            }
        }
        for (int i = 1; i <= n; i++) {  // 每一门语言都去尝试
            cnt = 0;
            Arrays.fill(hp, false); // 一开始所有人都没有学习这门语言
            for (int j = 0; j < m; j++) {
                if (sets.get(j).contains(i)) {  // 已经会这门语言了
                    hp[j + 1] = true;
                }
            }

            for (int j = 0; j < k; j++) {
                int a = friendships[j][0], b = friendships[j][1];
                if (h[j] == false && (!hp[a] || !hp[b])) {  // a没学或b没学
                    if (!hp[a]) {
                        hp[a] = true;
                        cnt++;
                    }
                    if (!hp[b]) {
                        hp[b] = true;
                        cnt++;
                    }
                }
            }
            ans = Math.min(ans, cnt);
        }
        return ans;
    }
}
